package com.lw.leetcode.back.c;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 996. 正方形数组的数目
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/8 16:52
 */
public class NumSquarefulPerms {

    public static void main(String[] args) {
        NumSquarefulPerms test = new NumSquarefulPerms();
        // 输入：[1,17,8]
        //输出：2
        //解释：
        //[1,8,17] 和 [17,8,1] 都是有效的排列。
        //示例 2：
        //
        //输入：[2,2,2]
        //输出：1

        // 2
//        int[] arr = {1,17,8};

        // 1
//        int[] arr = {2,2,2};

        // 4
        int[] arr = {0, 0, 0, 1, 1, 1};

        // 0
//        int[] arr = {12, 34567, 45, 2345, 65, 28, 97, 3490, 45673, 1358, 2, 4};

        int i = test.numSquarefulPerms(arr);
        System.out.println(i);
    }


    private int length;
    private long[] arr;
    private int[] nums;
    private int count = 0;

    public int numSquarefulPerms(int[] nums) {
        Arrays.sort(nums);
        length = nums.length;
        arr = new long[length];
        this.nums = nums;
        find(0);
        return count;
    }

    private void find(int index) {
        if (index == length) {
            count++;
            return;
        }
        int last = -1;
        for (int i = 0; i < length; i++) {
            int n = nums[i];
            if (n != -1 && n != last) {
                nums[i] = -1;
                if (index == 0) {
                    arr[index] = n;
                    find(index + 1);
                } else {
                    long l = arr[index - 1] + n;
                    long m = (long) Math.pow(l, 0.5);
                    if (m * m == l) {
                        arr[index] = n;
                        find(index + 1);
                    }
                }
                last = n;
                nums[i] = n;
            }
        }
    }

}
